#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <assert.h>


void _MergeSort(int* arr, int left, int right, int* tmp)
{
	if (left >= right)
	{
		return;
	}
	int mid = (left + right) / 2;
	_MergeSort(arr, left, mid , tmp);
	_MergeSort(arr, mid+1, right , tmp);

	int begin1 = left;
	int i = left;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = right;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[i++] = arr[begin1++];
		}
		if (arr[begin1] > arr[begin2])
		{
			tmp[i++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	while (left <= right)
	{
		arr[left] = tmp[left];
		left++;
	}
}


void MergeSort(int* arr,int n)
{
	int* tmp = (int*)malloc(sizeof(n));
	_MergeSort(arr, 0, n - 1, tmp);

}

void CountSort(int* arr, int n)
{
	int max, min;
	max = min = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}
	int range = max - min + 2;
	int* tmp = (int*)malloc(sizeof(int) * range);
	assert(tmp);
	memset(tmp, 0, sizeof(int)*range);
	for (int i = 0; i < n; i++)
	{
		tmp[arr[i]]++;
	}
	int index = 0;
	while (index < range)
	{
		if (tmp[index] != 0)
		{
			std::cout << index << std::endl;
			tmp[index]--;
		}
		index++;
	}
}

void test()
{
	int arr[] = { 10,6,7,1,3,9,4,2 };
	int n = sizeof(arr) / sizeof(int);
	//MergeSort(arr, n);
	//for (int i = 0; i < n; i++)
	//{
	//	std::cout << arr[i] << " ";
	//}
	CountSort(arr, n );
}

int main()
{
	test();
}